Digital signatures are useful in commerce that is conducted at a distance. It is A often useful and necessary to communicate one's offer or acceptance of a commercial transaction in writing, using any one of the many forms of electronic communications presently available, such as facsimile (hereinafter “fax”), electronic mail (hereinafter “e-mail”), and documents and/or images in various electronic formats. In particular, it is now the law in the United States that electronic signatures carry the same legal effect as a handwritten signature provided in the “old-fashioned” manner by the use of pen and ink in interstate and international commerce, with certain exceptions (See the Electronic Signatures in Global and National Commerce Act, Public Law 106-229 (2000)). However, the concept of digital signatures is not new, having been proposed in 1976 by Diffie and Hellman.
In the case of traditional handwritten signatures, authentication can be provided by having a signature witnessed, for example by a notary, by the analysis of handwriting samples by experts, and the like. In the case of a digital signature, the problem is to authenticate a “signature” represented by a series of symbols, such as 1's and 0's, transmitted over an insecure communication channel from an unseen source. One major goal of classical cryptography is to certify the origin of a message.
In this document, we shall follow the conventional usage in the literature of quantum computing, in which a first person, called Alice, and a second person, called Bob, are individuals who perform the various manipulations that are discussed. The names Alice and Bob have become customary in such discussions, rather than using arbitrary names or designations.
Classical digital signature schemes can be created out of many one-way functions. ƒ(x) is a one-way function if it is easy to compute ƒ(x) given x, but computing x given ƒ(x) is very difficult. This allows the following digital signature scheme: Alice chooses k0 and k1, and publicly announces ƒ, (0,ƒ(k0)) and (1,ƒ(k1)). Later, to sign a single bit b (where b is 0 or 1), Alice presents (b, kb). The recipient can easily computer ƒ(kb) and check that it agrees with Alice's earlier announcement, and since k0 and k1 were known only to Alice, this certifies that she must have sent the message.
The use of public key digital signature schemes, in which a publicly available key is used to prepare a message and/or signature, and a privately held key is required to decode the message and/or signature, is one approach to providing digital signatures based on a one-way function. The security of all such public key digital signature schemes presently depends on the inability of a forger to solve certain difficult mathematical problems, such as factoring large numbers. The basis for such public key systems is the belief that the problem to be solved involves such great computational difficulty that present computer systems cannot solve the problem in a reasonable period of time. However, improved computer systems, or improved computational methods, can provide the capability to solve such problems in reasonable time periods. In particular, there is no known mathematical proof that such classical systems for the provision of digital signatures are incapable of being defeated by an adversary with sufficient computational power and mathematical capability. For example, with a quantum computer, the solution of certain difficult problems, such as factoring, becomes tractable. With the use of quantum computers, digital signature systems that operate according to classical principles can be defeated, and signatures can be forged. In the terminology of those of skill in the cryptologic arts, the provision of a false signature that is accepted as genuine is referred to as existential forgery.